import java.util.LinkedList;
import java.util.Queue;

/**
 * 多源最短路问题
 */
public class Solution2 {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};

    /**
     * 01矩阵
     * @param mat
     * @return
     */
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dist = new int[m][n]; // 记录结果
        boolean[][] vis = new boolean[m][n]; // 当前位置是否访问过
        Queue<int[]> queue = new LinkedList<>();
        // 1. 将所有起点加入到队列中
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    // vis[i][j] = true;
                    queue.add(new int[] {i, j});
                }
            }
        }
        // 2. 一层一层向外扩展
        int step = 0;
        while(!queue.isEmpty()) {
            step++;
            int sz = queue.size();
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                int a = tmp[0];
                int b = tmp[1];
                for(int i = 0; i < 4; i++) {
                    int x = a + dx[i];
                    int y = b + dy[i];
                    if (x >= 0 && x < m
                            && y >= 0 && y < n
                            && mat[x][y] == 1 && !vis[x][y]) {
                        dist[x][y] = step;
                        vis[x][y] = true;
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
        return dist;
    }

    /**
     * 飞地的数量
     * @param grid
     * @return
     */
    public int numEnclaves(int[][] grid) {
        int sum = 0;
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        // 1. 统计总陆地单元格数量
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    sum++;
                }
            }
        }
        // 将边缘陆地加入到队列中
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < m; i++) {
            if (grid[i][0] == 1 && !vis[i][0]) {
                queue.add(new int[]{i, 0});
                vis[i][0] = true;
            }
            if (grid[i][n - 1] == 1 && !vis[i][n - 1]) {
                queue.add(new int[]{i, n - 1});
                vis[i][n - 1] = true;
            }
        }
        for(int j = 1; j < n - 1; j++) {
            if (grid[0][j] == 1 && !vis[0][j]) {
                queue.add(new int[]{0, j});
                vis[0][j] = true;
            }
            if (grid[m - 1][j] == 1 && !vis[m - 1][j]) {
                queue.add(new int[]{m - 1, j});
                vis[m - 1][j] = true;
            }
        }
        // 一层一层向外扩展
        while(!queue.isEmpty()) {
            int sz = queue.size();
            sum -= sz;
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                int a = tmp[0];
                int b = tmp[1];
                for(int i = 0; i < 4; i++) {
                    int x = a + dx[i];
                    int y = b + dy[i];
                    if (x >= 0 && x < m
                            && y >= 0 && y < n
                            && grid[x][y] == 1 && !vis[x][y]) {
                        vis[x][y] = true;
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
        return sum;
    }

    /**
     * 地图中的最高点
     * @param isWater
     * @return
     */
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;
        boolean[][] vis = new boolean[m][n];
        int[][] high = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        // 1. 将所有水域放入队列
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    queue.add(new int[]{i, j});
                }
            }
        }
        // 2. 一层一层向外扩展
        int step = 0;
        while(!queue.isEmpty()) {
            step++;
            int sz = queue.size();
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                int a = tmp[0];
                int b = tmp[1];
                for(int i = 0; i < 4; i++) {
                    int x = a + dx[i];
                    int y = b + dy[i];
                    if (x >= 0 && x < m
                            && y >= 0 && y < n
                            && isWater[x][y] == 0 && !vis[x][y]) {
                        high[x][y] = step;
                        vis[x][y] = true;
                        queue.add(new int[] {x, y});
                    }
                }
            }
        }
        return high;
    }

    /**
     * 地图分析
     * @param grid
     * @return
     */
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        boolean[][] vis = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<>();
        // 1. 将所有陆地放入队列
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.add(new int[]{i, j});
                }
            }
        }
        // 处理特殊情况
        if (queue.size() == 0 || queue.size() == n * n) {
            return -1;
        }
        // 2. 一层一层向外扩展
        int step = 0;
        while(!queue.isEmpty()) {
            step++;
            int sz = queue.size();
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                int a = tmp[0];
                int b = tmp[1];
                for(int i = 0; i < 4; i++) {
                    int x = a + dx[i];
                    int y = b + dy[i];
                    if (x >= 0 && x < n
                            && y >= 0 && y < n
                            && grid[x][y] == 0 && !vis[x][y]) {
                        vis[x][y] = true;
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
        return step - 1;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[][] mat = {{1, 0, 0}, {0, 0, 0}, {0, 0, 0}};
//        solution2.updateMatrix(mat);
//        solution2.numEnclaves(mat);
        solution2.maxDistance(mat);
    }
}
